package ch10;

import java.util.Scanner;
class Node {
	public int leftcnt = 0;
	public Node left = null, right = null, parent = null;
	public int value = -1;
	
	public Node(int value) {
		this.value = value;
	}
}

public class Ch10_8 {
	
	
	private Node root;
	
	public Ch10_8() {
		root = null;
	}
	
	public Ch10_8(Node root) {
		this.root = root;
	}
	
	public void track(Node z) {
		Node y = null;
		Node x = root;
		while (x != null) {
			y = x;
			if (x.value > z.value) {
				x.leftcnt++;
				x = x.left;
			} else {
				x = x.right;
			}
		}
		z.parent = y;
		if (y == null) {
			root = z;
		} else if (y.value > z.value) {
			y.left = z;
		} else {
			y.right = z;
		}
	}
	
	public int getRank(int x) {
		return getRank(x, root);
	}
	
	private int getRank(int x, Node n) {
		if (null == n) {
			return -1;
		}
		if (x < n.value) {
			return getRank(x, n.left);
		} else if (x > n.value){
			int rank = 0;
			int right = getRank(x, n.right);
			if (right == -1) {
				rank = -1;
			} else {
				rank += 1 + n.leftcnt + right;
			}
			return rank;
		} else {
			return n.leftcnt + 1 + getRank(x, n.right);
		}
	}
	
	public static void main(String[] args) {
		Ch10_8 test = new Ch10_8();
		Scanner scanner = new Scanner(System.in);
		int i = -1;
		do {
			System.out.println("Please enter an integer, -1 to quit");
			i = scanner.nextInt();
			if (i != -1) {
				Node n = new Node(i);
				test.track(n);
				int rank = test.getRank(i);
				System.out.println("rank(" + i + ") is " + rank);
			}
		} while (i != -1);
	}
}
